/*
 * Delaunay三角剖分算法库
 */
define(["require", "exports", "./Topology","./Geometry"], function(require, exports, Topology, Geometry) {
	function Delaunay() {
	}
	var topology = new Topology();
	var geometry = new Geometry();
	/*
	 * 点线面几何模型
	 */
	var Point = geometry.Point;
	
	var Line = geometry.Line;

	var Polygon = geometry.Polygon;

	/*
	 * 用点切割多边形
	 * 切割线要求：点必须在多边形内部，点根据多边形所有节点的连线来切割多边形
	 * polygon 表示被切割的多边形，数据结构为 Polygon
	 * point 表示插入的内部点，数据结构为 Point
	 */
	Delaunay.prototype.polygonSplitByPoint = function(polygon, point) {
		var chilPolgons = []; //被切割后的多边形
		var vertices = polygon.getVertices();
		var cutlines = []; //切割线
		var edgelines = []; //多边形边线
		//判断点与多边形的关系，如果点不在多边形内容则结束
		var rel = topology.PolygonPointRel(vertices.map(function(item) {
			return item.getCoordinate()
		}), point.getCoordinate());
		if(rel != "in")
			return;

		for(var i in vertices) {
			var line = new Line();
			line.setVertices(vertices[i], point);
			cutlines.push(line);
		}
		edgelines = polygon.getLines();
		//遍历边缘线
		for(var i in edgelines) {
			var edgeline = edgelines[i];
			var edgepoints = edgeline.getVertices();
			//查找与该边缘线相接的切割线
			var addlines = cutlines.filter(function(item) {
				var newpoints = item.getVertices();
				var newids = newpoints.map(function(item2) {
					return item2.getId()
				});
				var edgeids = edgepoints.map(function(item2) {
					return item2.getId()
				});
				var ids = newids.concat(edgeids);
				var checkids = {};
				for(var j in ids) {
					if(checkids[ids[j]] == null) {
						checkids[ids[j]] = 1;
					} else
						checkids[ids[j]]++;
				}
				for(var j in checkids) {
					if(checkids[j] > 1)
						return true;
				}
				return false;
			});
			var newpolygon = new Polygon();
			newpolygon.constructByLines([addlines[0], addlines[1], edgeline]);
			chilPolgons.push(newpolygon);
		}
		return chilPolgons;
	};

	/*
	 * 合并多边形
	 * polygons:需要合并的多边形，数据结构为 Polygon
	 */
	Delaunay.prototype.mergePolygons = function(mergepolygons) {
		var alllines = [];
		var edgelines = [];
		var mergepolygons = mergepolygons;
		for(var i in mergepolygons) {
			var lines = mergepolygons[i].getLines();
			for(var j in lines) {
				alllines.push(lines[j]);
			}
		}
		//判断每条线上相接的多边形，如果相接多边形属于合并多边形的数量为一，则表示为边线并存入edgelines中
		for(var i in alllines) {
			var line = alllines[i];
			var polygons = line.getPolygons();
			var isEdgeLine = true;
			//记录该线段周围相邻的多边形数
			var containNum = 0;
			for(var j in polygons) {
				var polygon = polygons[j];
				var num = (mergepolygons.filter(function(item) {
					return(item.getId() == polygon.getId())
				})).length;
				if(num > 0)
					containNum++;
				if(containNum == 2) {
					isEdgeLine = false;
					break;
				}
			}
			if(isEdgeLine == true)
				edgelines.push(line);
		}
		//将分析出的边线合并成多边形
		var outPolygon = new Polygon();
		outPolygon.constructByLines(edgelines);
		return outPolygon;
	}

	/*
	 * Delaunay三角剖分（Bowyer-Watson算法）
	 * points: 表示输入点集，数据结构 [[x1,y1],[x2,y2],、、、]
	 */
	Delaunay.prototype.DelaunayTriangulation = function(points) {
		var DelaunayTri_List = [];
		var Point_List = [];
		for(var i in points) {
			Point_List.push({
				"id": i,
				"coordinate": points[i]
			});
		}
		//外包边缘的点集
		var outPoint_List = topology.OutConvexPolgon(points);
		for(var i in outPoint_List) {
			var outPoint = outPoint_List[i];
			Point_List = Point_List.filter(function(item) {
				return(item.id != outPoint.index)
			});
		}
		var line_list = [];
		var outPoints = [];

		for(var i in outPoint_List)
			outPoints.push(new Point(outPoint_List[i].coordinate, outPoint_List[i].index));

		for(var i = 0; i < outPoints.length; i++) {
			var j = i + 1;
			if(j == outPoints.length)
				j = 0;
			var point1 = outPoints[i];
			var point2 = outPoints[j];
			var line = new Line();
			line.setVertices(point1, point2);
			line_list.push(line);
		}
		var firstPolygon = new Polygon();
		firstPolygon.constructByLines(line_list);
		DelaunayTri_List = [firstPolygon];

		//上面已完成初始多边形的构建，下面开始插点
		for(var i = 0; i < Point_List.length; i++) {
			var insertPoint = new Point(Point_List[i].coordinate, Point_List[i].id);
			//判断插入点落入多边形是否为三角形，如果不是三角形则直接切割
			var overlayPolygon = DelaunayTri_List.filter(function(item) {
				var polygonPoints = item.getVertices().map(function(item2) {
					return item2.getCoordinate()
				});
				var rel = topology.PolygonPointRel(polygonPoints, insertPoint.getCoordinate());
				if(rel == "in")
					return true;
				else
					return false;
			}.bind(this));
			//获取所覆盖的多边形
			overlayPolygon = overlayPolygon[0];
			//如果该多边形不为三角形
			if(overlayPolygon != null && overlayPolygon.getLines().length > 3) {
				//直接分割多边形
				var chiltri = this.polygonSplitByPoint(overlayPolygon, insertPoint);
				for(var j in chiltri) {
					DelaunayTri_List.push(chiltri[j]);
				}
				DelaunayTri_List = DelaunayTri_List.filter(function(item) {
					return item.getId() != overlayPolygon.getId()
				});
				overlayPolygon.destroy();
				continue;
			}
			//查找插入点周围的影响三角形
			var influnceTris = DelaunayTri_List.filter(function(item) {
				var points = item.getVertices().map(function(item2) {
					return item2.getCoordinate()
				});
				var circle = topology.TriangleGetCircumcircle(points);
				var radius = circle.radius;
				var point = circle.coordinate;
				var inPoint = insertPoint.getCoordinate();
				var dis = Math.sqrt(Math.pow(inPoint[0] - point[0], 2) + Math.pow(inPoint[1] - point[1], 2));
				if(dis < radius)
					return true;
				else
					return false;
			}.bind(this));
			//将影响三角形合并成多边形
			var mergePolygon = this.mergePolygons(influnceTris);
			//销毁影响三角形数据对象
			for(var j in influnceTris) {
				var tri = influnceTris[j];
				DelaunayTri_List = DelaunayTri_List.filter(function(item) {
					return tri.getId() != item.getId()
				});
				tri.destroy();
			}
			//将多边形分割，并将分割后的三角形存入三角形列表中
			var chiltri = this.polygonSplitByPoint(mergePolygon, insertPoint);
			for(var j in chiltri) {
				DelaunayTri_List.push(chiltri[j]);
			}
			//销毁多边形对象
			mergePolygon.destroy();
		}
		return DelaunayTri_List;
	}
	return Delaunay;
});